package algorithm.leetcode.medium;

/*
 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 */

import java.util.*;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2021/1/6
 */
public class Question347 {

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        Question347 question = new Question347();
        int[] ints = question.topKFrequent(nums, 2);
        System.out.println(Arrays.toString(ints));
    }

    public int[] topKFrequent(int[] nums, int k) {
        // key：num value：出现次数
        Map<Integer, Integer> map = new HashMap<>(8);
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
                continue;
            }
            map.put(num, 1);
        }

        // 优先级队列 最小堆 升序
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(map::get));

        for (Integer key : map.keySet()) {
            if (pq.size() < k) {
                // 小于K个的时候 直接添加
                pq.add(key);
            } else if (map.get(key) > map.get(pq.peek())) {
                // 如果之后的出现次数 大于 之前添加 移除然后添加
                pq.remove();
                pq.add(key);
            }
        }

        // 返回结果
        int[] res = new int[k];
        int i = 0;
        while (i < k) {
            res[i++] = pq.remove();
        }
        return res;
    }

}
